package 剑指专题.队列栈;


/*
 * Author：江松
 * Date：2023/3/27 10:42
 *
 滑动窗口的最大值:
 1，暴力枚举区间，找到最大值
 2，单调队列：队列递减，队头为当前最大值（后面的比前面大，前边就没必要存在了）
 同时需要检查队头是否过期
 */

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Main5 {

    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer>res=new ArrayList<>();
        //双向队列存放对应位置的坐标
        Deque<Integer>queue=new LinkedList<>();
        for(int i=0;i<num.length;++i){
            while(!queue.isEmpty()&&num[i]>num[queue.peekLast()]){
                queue.pollLast();
            }
            queue.offerLast(i);
            //检查过期
            if(queue.peekFirst()+size<=i){
                queue.pollFirst();
            }
            if(i>=size){
                res.add(num[queue.peekFirst()]);
            }
        }
        return res;
    }


    /*
    //暴力法
        public ArrayList<Integer> maxInWindows(int [] num, int size) {
        int len=num.length;
        ArrayList<Integer> ans=new ArrayList<>();
        if(size==0)return ans;
        for(int i=0;i<len-size+1;++i){
            int mx=num[i];
            for(int j=i+1;j<i+size;++j){
                if(mx<num[j]){
                    mx=num[j];
                }
            }
            ans.add(mx);
        }
        return ans;
    }
     */
}
